package main

import (
	"fmt"
	. "local/algorithm/util"
)

/**
删除二叉搜索树的一个节点，利用二分查找找到节点后，该节点由三种情况
1.节点是叶子节点
	直接略过该节点，向上一级返回nil
2.节点是非叶子节点，单子树
	向上一级该节点的子树根节点
3.节点是非叶子节点，双子树
	拷贝节点后继节点(右子树最小的节点)，然后删除右子树最小的节点,向上一级返回后继节点
	ps: 使用前驱或后继节点都可以，此处实现用的后继节点

见https://leetcode-cn.com/problems/delete-node-in-a-bst/solution/yong-qian-qu-huo-zhe-hou-ji-jie-dian-zi-shu-dai-ti/
*/

func main() {
	root := generate([]int{1, 2, 3})
	deleteNode(root, 3)
	fmt.Println(root)
}

func generate() *TreeNode {
	//[5,3,6,2,4,null,7]
	root := &TreeNode{Val: 5}
	root.Left = &TreeNode{Val: 3}
	root.Right = &TreeNode{Val: 6}
	root.Left.Left = &TreeNode{Val: 2}
	root.Left.Right = &TreeNode{Val: 4}
	root.Right.Right = &TreeNode{Val: 7}
	return root
}

func deleteNode(root *TreeNode, key int) *TreeNode {
	if root == nil {
		return root
	}

	if root.Val == key {
		if root.Left == nil && root.Right == nil { // 如果是叶子节点
			return nil
		} else if root.Left == nil { // 如果是非叶子单子树
			return root.Right
		} else if root.Right == nil {
			return root.Left
		} else { // 如果是非叶子双子树节点
			successor := findMinNode(root.Right)
			successor_copy := &TreeNode{Val: successor.Val} // 这里必须生成新节点successor_copy，对原节点执行successor.Left=root.Left会改变原有树结构，另外下一步会对该节点进行删除
			successor_copy.Left = root.Left
			successor_copy.Right = removeMinNode(root.Right)

			return successor_copy
		}
	} else if key < root.Val {
		root.Left = deleteNode(root.Left, key)
		return root
	} else {
		root.Right = deleteNode(root.Right, key)
		return root
	}
}

func findMinNode(root *TreeNode) *TreeNode {
	if root == nil {
		return root
	}

	for root.Left != nil {
		root = root.Left
	}

	return root
}

// 删除最小节点，并返回树新的根节点
func removeMinNode(root *TreeNode) *TreeNode {
	if root == nil {
		return root
	}

	if root.Left == nil {
		tmp := root.Right
		root.Right = nil
		return tmp
	}

	root.Left = removeMinNode(root.Left)
	return root
}
